package gold.digger;

import java.util.*;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1562 {
    public long startExecuteTime = System.currentTimeMillis();


    /**
     * 题目是好题目，就是案例真想骂娘
     */
    class Solution {
        public int findLatestStep(int[] arr, int m) {
            TreeSet<Integer> set = new TreeSet<>();
            set.add(0);
            set.add(arr.length + 1);
            if (arr.length == m) return arr.length;
            int n = arr.length;
            for (int i = n - 1; i >= 0; i--) {
                int index = arr[i];
                int a = set.lower(index);
                int b = set.higher(index);
                if (index - a - 1 == m || b - index - 1 == m) {
                    return i;
                }
                set.add(index);
            }
            return -1;
        }
    }


    class Solution_Wrong_Understanding {
        public int findLatestStep(int[] arr, int m) {
            if (arr.length == m) return m;
            int[] occ = new int[arr.length + 1];
            int maxSeqLen = 0, step = 0;
            boolean hasMatch = false;
            for (int i : arr) {
                step++;
                int nextPosLen = (i < arr.length && occ[i + 1] > 0) ? occ[i + 1] : 0;
                occ[i] = nextPosLen + 1;
                int j = i - 1;
                while (j > 0 && occ[j] > 0) {
                    occ[j] = occ[j + 1] + 1;
                    j--;
                }

                maxSeqLen = Math.max(maxSeqLen, occ[j + 1]);
                if (maxSeqLen == m) hasMatch = true;
                if (maxSeqLen > m) return hasMatch ? step : -1;
            }

            return -1;
        }
    }

    public void run() {
//        System.out.println(new Solution().findLatestStep(InputUtil.toIntegerArray("[3,5,1,2,4]"), 1));
//        System.out.println(new Solution().findLatestStep(InputUtil.toIntegerArray("[3,1,5,4,2]"), 2));
//        System.out.println(new Solution().findLatestStep(InputUtil.toIntegerArray("[1]"), 1));
//        System.out.println(new Solution().findLatestStep(InputUtil.toIntegerArray("[2,1]"), 2));
        System.out.println(new Solution().findLatestStep(InputUtil.toIntegerArray("[1,2]"), 1));
    }

    public static void main(String[] args) throws Exception {
        LC1562 an = new LC1562();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}


